package np.com.baralsujan.algorithms;

public class BinaryTree {

	private Node root;

	public BinaryTree() {
		root = null;
	}

	public BinaryTree(int value) {
		root = new Node(value);
	}

	public void insert(int data) {
		root = insert(root, data);
	}

	public Node insert(Node node, int data) {
		if(node == null) {
			return new Node(data);
		}
		if (node.value >= data) {
			node.left = insert(node.left, data);
		} else {
			node.right = insert(node.right, data);
		}
		return node;
	}

	public boolean lookup(Node node, int value) {
		if (node == null) {
			return false;
		}
		if (node.value == value) {
			return true;
		}
		if (value > node.value) {
			return lookup(node.right, value);
		} else {
			return lookup(node.left, value);
		}
	}

	public int size() {
		return size(root);
	}

	private int size(Node node) {
		if(node == null) {
			return 0;
		} else {
			return 1 + size(node.left) + size(node.right);
		}
	}

	public int maxDepth() {
		return maxDepth(root);
	}

	private int maxDepth(Node node) {
		if(node == null) {
			return 0;
		}
		int leftDepth = 1 + maxDepth(node.left);
		int rightDepth = 1 + maxDepth(node.right);
		return leftDepth > rightDepth ? leftDepth: rightDepth;
	}

	public int minValue() {
		return minValue(root);
	}

	private int minValue(Node node) {
		if(node == null) {
			return 0;
		}
		if(node.left == null) {
			return node.value;
		} else {
			return minValue(node.left);
		}
	}

	public void printTree() {
		System.out.println();
		printTree(root);
	}

	private void printTree(Node node) {
		if(node == null) {
			return;
		}
		printTree(node.left);
		System.out.print(node.value);
		printTree(node.right);
	}

	public void printPostOrder() {
		System.out.println();
		printPostOrder(root);
	}

	private void printPostOrder(Node node) {
		if(node == null) {
			return;
		}
		printPostOrder(node.left);
		printPostOrder(node.right);
		System.out.print(node.value);
	}

	public Node getRoot() {
		return root;
	}

	public static class Node {
		private Node left;
		private Node right;
		private final int value;

		Node(int data) {
			value = data;
			left = null;
			right = null;
		}

		public int getValue() {
			return value;
		}
	}

}
